class Solution
{
public:
    int shortestSubarray(vector<int> &nums, int k)
    {
        int n = nums.size();
        vector<long long> prefixSum(n + 1);
        prefixSum[0] = 0LL;
        for (int i = 0; i < n; ++i)
        {
            prefixSum[i + 1] = prefixSum[i] + nums[i];
        }
        deque<int> q;
        q.push_back(0);
        int minLen = -1;
        for (int i = 1; i <= n; ++i)
        {
            long long curSum = prefixSum[i];
            while (!q.empty())
            {
                long long subSum = curSum - prefixSum[q.front()];
                if (subSum >= k)
                {
                    int len = i - q.front();
                    if (minLen == -1)
                    {
                        minLen = len;
                    }
                    else
                    {
                        minLen = min(minLen, len);
                    }
                    if (minLen == 1)
                    {
                        return 1;
                    }
                    q.pop_front();
                }
                else
                {
                    break;
                }
            }
            while (!q.empty())
            {
                if (curSum <= prefixSum[q.back()])
                {
                    q.pop_back();
                }
                else
                {
                    break;
                }
            }
            q.push_back(i);
        }
        return minLen;
    }
};